//
//  main.m
//  GetKthFromEnd22
//
//  Created by Xuyang Li on 2020/8/3.
//  Copyright © 2020 李旭阳[产品技术中心]. All rights reserved.
//  剑指 Offer 22. 链表中倒数第k个节点


#import <Foundation/Foundation.h>
#import "ListNode.h"

/*
 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
 例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。
 */

//双指针
ListNode *getKthFromEnd(ListNode *head, NSInteger k) {
    ListNode *former = head;
    ListNode *latter = head;
    
    for (NSInteger i = 0; i < k; i++) {
        if (!former) {
            return nil;
        }
        former = former.next;
    }
    
    while (former) {
        former = former.next;
        latter = latter.next;
    }
    
    return latter;
}

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        // insert code here...
        NSLog(@"Hello, World!");
    }
    return 0;
}
